package com.shm.leetcode;

/**
 * 1020. 飞地的数量
 * 给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
 *
 * 一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
 *
 * 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
 * 输出：3
 * 解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
 * 示例 2：
 *
 *
 * 输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
 * 输出：0
 * 解释：所有 1 都在边界上或可以到达边界。
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 500
 * grid[i][j] 的值为 0 或 1
 * @author SHM
 */
public class NumEnclaves {

    int[][] direction = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    int m,n;
    boolean[][] visited;

    /**
     * 方法一：深度优先搜索
     * 根据飞地的定义，如果从一个陆地单元格出发无法移动到网格边界，则这个陆地单元格是飞地。因此可以将所有陆地单元格分成两类：第一类陆地单元格和网格边界相连，这些陆地单元格不是飞地；第二类陆地单元格不和网格边界相连，这些陆地单元格是飞地。
     *
     * 我们可以从网格边界上的每个陆地单元格开始深度优先搜索，遍历完边界之后，所有和网格边界相连的陆地单元格就都被访问过了。然后遍历整个网格，如果网格中的一个陆地单元格没有被访问过，则该陆地单元格不和网格的边界相连，是飞地。
     *
     * 代码实现时，由于网格边界上的单元格一定不是飞地，因此遍历网格统计飞地的数量时只需要遍历不在网格边界上的单元格。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(mn)O(mn)，其中 mm 和 nn 分别是网格 \textit{grid}grid 的行数和列数。深度优先搜索最多访问每个单元格一次，需要 O(mn)O(mn) 的时间，遍历网格统计飞地的数量也需要 O(mn)O(mn) 的时间。
     *
     * 空间复杂度：O(mn)O(mn)，其中 mm 和 nn 分别是网格 \textit{grid}grid 的行数和列数。空间复杂度主要取决于 \textit{visited}visited 数组和递归调用栈空间，空间复杂度是 O(mn)O(mn)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/number-of-enclaves/solution/fei-di-de-shu-liang-by-leetcode-solution-nzs3/
     * @param grid
     * @return
     */
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(grid,i,0);
            dfs(grid,i,n-1);
        }
        for (int i = 1; i < n-1; i++) {
            dfs(grid,0,i);
            dfs(grid,m-1,i);
        }
        int enclaves = 0;
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (grid[i][j]==1&&!visited[i][j]){
                    enclaves++;
                }
            }
        }
        return enclaves;
    }

    void dfs(int[][] grid,int row,int col){
        if (row<0||row>=m||col<0||col>=n||grid[row][col]==0||visited[row][col]){
            return;
        }
        visited[row][col]=true;
        for (int[] ints : direction) {
            dfs(grid,row+ints[0],col+ints[1]);
        }
    }


    /**
     * 方法三：并查集
     * 除了深度优先搜索和广度优先搜索的方法以外，也可以使用并查集判断每个陆地单元格是否和网格边界相连。
     *
     * 并查集的核心思想是计算网格中的每个陆地单元格所在的连通分量。对于网格边界上的每个陆地单元格，其所在的连通分量中的所有陆地单元格都不是飞地。如果一个陆地单元格所在的连通分量不同于任何一个网格边界上的陆地单元格所在的连通分量，则该陆地单元格是飞地。
     *
     * 并查集的做法是，遍历整个网格，对于网格中的每个陆地单元格，将其与所有相邻的陆地单元格做合并操作。由于需要判断每个陆地单元格所在的连通分量是否和网格边界相连，因此并查集还需要记录每个单元格是否和网格边界相连的信息，在合并操作时更新该信息。
     *
     * 在遍历网格完成并查集的合并操作之后，再次遍历整个网格，通过并查集中的信息判断每个陆地单元格是否和网格边界相连，统计飞地的数量。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(mn \times \alpha(mn))O(mn×α(mn))，其中 mm 和 nn 分别是网格 \textit{grid}grid 的行数和列数，\alphaα 是反阿克曼函数。这里的并查集使用了路径压缩和按秩合并，单次操作的时间复杂度是 O(\alpha(mn))O(α(mn))，因此整个网格的并查集操作的时间复杂度是 O(mn \times \alpha(mn))O(mn×α(mn))，并查集操作之后需要 O(mn \times \alpha(mn))O(mn×α(mn)) 的时间再次遍历网格统计飞地的数量，因此总时间复杂度是 O(mn \times \alpha(mn))O(mn×α(mn))。
     *
     * 空间复杂度：O(mn)O(mn)，其中 mm 和 nn 分别是网格 \textit{grid}grid 的行数和列数。并查集需要 O(mn)O(mn) 的空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/number-of-enclaves/solution/fei-di-de-shu-liang-by-leetcode-solution-nzs3/
     * @param grid
     * @return
     */
    public int numEnclaves_1(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==1){
                    int index = i*n+j;
                    if (j+1<n&&grid[i][j+1]==1){
                        uf.union(index,index+1);
                    }
                    if (i+1<m&&grid[i+1][j]==1){
                        uf.union(index,index+n);
                    }
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (grid[i][j]==1&&!uf.isOnEdge(i*n+j)){
                    enclaves++;
                }
            }
        }
        return enclaves;
    }

    class UnionFind{
        int[] parent;
        boolean[] onEdge;
        int[] rank;

        public UnionFind(int[][] grid){
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m*n];
            onEdge = new boolean[m*n];
            rank = new int[m*n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j]==1){
                        int index = i*n+j;
                        parent[index] = index;
                        if (i==0||j==0||i==m-1||j==n-1){
                            onEdge[index] = true;
                        }
                    }
                }
            }
        }

        int find(int x){
            if (parent[x]!=x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            if (rootX!=rootY){
                if (rank[rootX]>rank[rootY]){
                    parent[rootY]=rootX;
                    onEdge[rootX] |= onEdge[rootY];
                }else if (rank[rootX]<rank[rootY]){
                    parent[rootX] = rootY;
                    onEdge[rootY] |= onEdge[rootX];
                }else {
                    parent[rootY] = rootX;
                    onEdge[rootX] |= onEdge[rootY];
                    rank[rootX]++;
                }
            }
        }

        boolean isOnEdge(int x){
            return onEdge[find(x)];
        }
    }
}
